package com.mengfou;


import sun.reflect.generics.tree.Tree;

import java.util.*;

class ListNode {
    ListNode next;
    int val;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class A {

    static class Sort {

        void quickSort(int[] nums) {
            quickSort(nums, 0, nums.length - 1);
        }

        void quickSort(int[] nums, int left, int right) {
            if (left < right) {
                int pivot = partition(nums, left, right);
                quickSort(nums, left, pivot - 1);
                quickSort(nums, pivot + 1, right);
            }
        }

        int partition(int[] nums, int left, int right) {
            int pivot = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= pivot) right--;
                swap(nums, left, right);
                while (left < right && nums[left] <= pivot) left++;
                swap(nums, left, right);
            }
            return left;
        }

        private void swap(int[] nums, int left, int right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }

        void insertSort(int[] nums) {
            for (int i = 1; i < nums.length; i++) {
                int current = nums[i];
                int j = i - 1;
                for (; j >= 0; j--) {
                    if (nums[j] > current) {
                        nums[j + 1] = nums[j];
                    } else {
                        break;
                    }
                }
                nums[j + 1] = current;
            }
        }

        public static void main(String[] args) {
            int[] a = new int[]{4, 1, 2, 9, 10, 0};
            Sort sort = new Sort();
            sort.quickSort(a);
            sort.printList(a);
        }


        void printList(int[] nums) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int num : nums) {
                stringBuilder.append(num).append("\t");
            }
            System.out.println(stringBuilder);
        }
    }

    void quickSort(int[] nums, int left, int right, int k) {
        if (left < right) {
            int pivot = partition(nums, left, right);
            if (pivot >= k) {
                quickSort(nums, left, pivot, k);
            } else {
                quickSort(nums, pivot + 1, right, k);
            }
        }
    }

    int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) right--;
            swap(nums, left, right);
            while (left < right && nums[left] <= pivot) left++;
            swap(nums, left, right);
        }
        return left;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        quickSort(nums, 0, n - 1, n - k);
        return nums[n - k];
    }


    public class TreeNode {
        int val;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode left;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;

            this.right = right;
        }
    }

    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        getSum(root, new ArrayDeque<Integer>());
        List<List<Integer>> result_ = new ArrayList<List<Integer>>();
        for (List<Integer> integers : result) {
            if(sum(integers) ==  targetSum) {
                result_.add(integers);
            }
        }
        return result_;
    }

    private int sum(List<Integer> integers) {
        int sum = 0;
        for (Integer integer : integers) {
            sum+=integer;
        }
        return sum;
    }

    private void getSum(TreeNode root, ArrayDeque<Integer> temp) {
        if(root == null) {
            return;
        }
        temp.add(root.val);
        if(root.left == null && root.right == null) {
            result.add(new ArrayList<Integer>(temp));
        }
        getSum(root.left, temp);
        getSum(root.right, temp);
        temp.removeLast();
    }

    public String addStrings(String num1, String num2) {
        num1 = reverse(num1);
        num2 = reverse(num2);
        StringBuilder result = new StringBuilder();
        int index = 0, ans = 0, len1 = num1.length(), len2 = num2.length();
        while(index < len1 || index < len2) {
            int val1 = 0, val2 = 0;
            if (index < len1) {
                val1 = num1.charAt(index) - '0';
            }
            if(index < len2) {
                val2 = num2.charAt(index) - '0';
            }
            int sum = val1 + val2 + ans;
            if(sum >= 10) {
                sum = sum % 10;
                ans = 1;
            } else {
                ans = 0;
            }
            result.append(sum);
            index++;
        }
        return reverse(result.toString());
    }

    private String reverse(String toString) {
        char[] chars = toString.toCharArray();
        StringBuilder stringBuffer = new StringBuilder();
        int index = chars.length - 1;
        while(index >= 0) {
            stringBuffer.append(chars[index]);
            index--;
        }
        return stringBuffer.toString();
    }

    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        queue.offer(root);

        while(!queue.isEmpty()) {
            while(!queue.isEmpty()) {
                TreeNode node1 = queue.poll();
                TreeNode node2 = queue.poll();
                if(node1 == null && node2 == null) {
                    continue;
                }
                if(node1 == null || node2 == null) {
                    return false;
                }
                if(node1.val != node2.val) {
                    return false;
                }
                queue.offer(node1.left);
                queue.offer(node2.right);
                queue.offer(node1.right);
                queue.offer(node2.left);
            }
        }
        return true;
    }

    private boolean check(TreeNode left, TreeNode right) {
        if(left == null && right == null) {
            return true;
        }
        if(left == null || right == null) {
            return false;
        }
        return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
    }



    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        getValues(root, result, 1);
        return result;
    }

    private void getValues(TreeNode root, List<Integer> result, int level) {
        if(root == null) {
            return;
        }
        if(result.size() + 1 == level) {
            result.add(root.val);
        }
        getValues(root.right, result, level + 1);
        getValues(root.left, result, level + 1);
    }



    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1, leftMax = 0, rightMax = 0;
        while(left < right) {
            if(height[left] < height[right]) {
                if(height[left] > leftMax) {
                    leftMax = height[left];
                } else {
                    ans += leftMax - height[left];
                }
                left++;
            } else {
                if(height[right] > rightMax) {
                    rightMax = right;
                } else {
                    ans += rightMax - height[right];
                }
                right--;
            }
        }
        return ans;
    }

    int sum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPath(root);
        return sum;
    }

    private int maxPath(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = Math.max(0, maxPath(root.left));
        int right = Math.max(0, maxPath(root.right));
        int AllVal = left + right + root.val;
        int SingleVal = root.val + Math.max(left, right);
        int val =  Math.max(root.val, Math.max(AllVal, SingleVal));
        sum = Math.max(sum, val);
        return val;
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
        if(root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        boolean leftHas = hasPathSum(root.left, targetSum - root.val);
        boolean rightHas = hasPathSum(root.right, targetSum - root.val);
        return leftHas || rightHas;
    }

    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode p = node;
        while(cnt > 0) {
            p = p.next;
            cnt--;
        }
        ListNode q = node;
        while(p.next != null) {
            p = p.next;
            q = q.next;
        }
        return q.next;
    }

    public static List<Integer> findTopKSmallest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num < minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        List<Integer> result = new ArrayList<Integer>(minHeap);
        Collections.sort(result);
        return result;
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        getAllIps(s, result, 0, 0);
        for (String s1 : result) {
            System.out.println(s1);
        }
        return null;
    }
    int[] segments = new int[4];
    private void getAllIps(String s, List<String> result, int seg, int segStart) {
        if(seg == 4) {
            if(s.length() == segStart) {
                StringBuilder stringBuilder = new StringBuilder();
                for (int i = 0; i < segments.length; i++) {
                    stringBuilder.append(segments[i]);
                    if(i < segments.length - 1) {
                        stringBuilder.append(".");
                    }
                }
                result.add(stringBuilder.toString());
            }
            return;
        }
        if(segStart == s.length()) {
            return;
        }
        if(s.charAt(segStart) == '0') {
            segments[seg] = 0;
            getAllIps(s, result, seg + 1, seg + 1);
            return;
        }
        StringBuffer b;
        int value = 0;
        for (int i = segStart; i < s.length(); i++) {

            value = value * 10 + s.charAt(i) - '0';
            if(value > 0 && value <= 255) {
                segments[seg] = value;
                getAllIps(s, result, seg + 1, i + 1);
            }
        }
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode();
        int index = 0;
        ListNode ptr = head;
        ListNode dummyPtr = dummy;
        while(ptr != null) {
            index = 0;
            ListNode qtr = ptr;
            ListNode q = null;
            while(index < k && ptr != null) {
                q = ptr;
                ptr = ptr.next;
                index++;
            }
            if(index == k) {
                if(q != null) {
                    q.next = null;
                    ListNode node = reverseList(qtr);
                    dummyPtr.next = node;
                    while(dummyPtr.next != null) {
                        dummyPtr = dummyPtr.next;
                    }
                }
            } else {
                dummyPtr.next = qtr;
            }
        }
        return dummy.next;
    }

    private ListNode reverseList(ListNode qtr) {
        ListNode dy = new ListNode();
        dy.next = null;
        while(qtr != null) {
            ListNode ptr = qtr.next;
            qtr.next = dy.next;
            dy.next = qtr;
            qtr = ptr;
        }
        return dy.next;
    }

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dict = new HashMap<Character, Integer>();
        int len = 0;
        for (int right = 0, left = 0; right < s.length(); right++) {
            char ele = s.charAt(right);
            while (dict.containsKey(ele)) {
                dict.remove(s.charAt(left));
                left++;
            }
            dict.put(ele, right);
            len = Math.max(right - left + 1, len);
        }
        return len;
    }


    static class LRUCache {

        private int mCapacity;
        private Map<Integer, Node> mContainer;
        private Node first, last;

        class Node {
            int value;
            Node next;
            Node pre;
        }

        public LRUCache(int capacity) {
            mContainer = new HashMap<>();
            mCapacity = capacity;
            first = new Node();
            last = new Node();
            first.pre = null;
            first.next = last;
            last.pre = first;
            last.next = null;
        }

        public int get(int key) {
            Node node = mContainer.get(key);
            if (node != null) {
                removeNode(node);
                addFirst(node);
                return node.value;
            }
            return -1;
        }

        private void addFirst(Node node) {
            node.next = first.next;
            node.pre = first;
            first.next.pre = node;
            first.next = node;
        }

        private void removeNode(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        public void put(int key, int value) {
            Node node = mContainer.get(key);
            if(node == null) {
                Node newNode = new Node();
                newNode.value = value;
                addFirst(newNode);
                mContainer.put(key, newNode);
                if(mContainer.size() >= mCapacity) {
                    int val = removeNodeLast();
                    mContainer.remove(val);
                }
            } else {
                node.value = value;
                removeNode(node);
                addFirst(node);
            }
        }

        private int removeNodeLast() {
            Node node = last.pre;
            removeNode(node);
            return node.value;
        }
    }

    public static void main(String[] args) {
        System.out.println(new A().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
    }

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max=dp[0];
        for(int i=1;i<nums.length;i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }

    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }


}


